/*
 * 题目描述：从控制中心找到一条前往问题节点的耗时最短的路径，在路径中将每个节点调整为半满状态，不够的从中心调，多的带回中心
 *
 * 输入：cmax 站点的最大容量 N 站点的数目 sp 问题节点的位置 M 道路的数目
 *      N个站点当前的自行车数量
 *      M行 道路（端点1 端点2 时间）
 *
 * 输出：最少的从中心调出的自行车数量 路径 最少的从送回中心的自行车数量
 *
 * 坑：默认条件为后面的节点的自行车无法往前调，比如路径中的各个节点自行车数量为 【起点 4 6】（半满为5），在到第一个节点的时候，就需要从中心调
 *     一辆自行车，在到第二个节点的时候需要向带回中心一辆自行车
 *
 */

#include <iostream>
#include <climits>
using namespace std;
int graph[500][500];
int weight[500] = {0};
int cmax,staNum,sp,roadNum;
int after[500];
int shortestPath[500];
int record[500];
int minTime = INT_MAX;
int finalDepth;
int fromMin = INT_MAX;
int toMin = INT_MAX;
void dfs(int cur, int time, int toBikes, int fromBikes, int depth) {
    if (cur == sp) {
        if (time < minTime) {
            toMin = toBikes;
            fromMin = fromBikes;
            minTime = time;
            finalDepth = depth;
            for (int i = 0; i <= staNum; i++) {
                shortestPath[i] = after[i];
            }
        } else if (time == minTime) {
            if (fromBikes < fromMin) {
                toMin = toBikes;
                fromMin = fromBikes;
                for (int i = 0; i <= staNum; i++) {
                    shortestPath[i] = after[i];
                }
                finalDepth = depth;
            }else if(fromBikes == fromMin){
                if(toBikes < toMin){
                    toMin = toBikes;
                    for (int i = 0; i <= staNum; i++) {
                        shortestPath[i] = after[i];
                    }
                    finalDepth = depth;
                }
            }
        }
        return;
    }
    if (time > minTime||fromBikes > fromMin) {
        return;
    }
    for (int i = 1; i <= staNum; i++) {
        if (record[i] != 0 && graph[cur][i] != 0) {
            record[i] = 0;
            after[cur] = i;
            if(weight[i] > cmax/2){
                dfs(i, time + graph[cur][i], toBikes + weight[i] - cmax / 2, fromBikes, depth + 1);

            }else{
                if (toBikes > cmax / 2 - weight[i]) {
                    dfs(i, time + graph[cur][i], toBikes - (cmax / 2 - weight[i]), fromBikes, depth + 1);

                }else{
                    dfs(i, time + graph[cur][i], 0, fromBikes + cmax / 2 - weight[i] - toBikes, depth + 1);

                }
            }
            record[i] = 1;
        }
    }
}
int main() {
    cin >> cmax>>staNum >> sp >> roadNum;
    for (int i = 1; i <= staNum; i++) {
        cin >> weight[i];
    }
    int i,j,time;
    while(roadNum--){
        cin >> i >> j >> time;
        graph[i][j] = graph[j][i] = time;
    }
    for (int i = 1; i <= staNum; i++) {
        record[i] = 1;
    }
    dfs(0, 0, 0, 0, 0);
    cout << fromMin << " ";
    cout << "0->";
    int cur = 0;
    while(true){
        if (shortestPath[cur] == sp) {
            cout << shortestPath[cur] << " ";
            break;
        }
        cout << shortestPath[cur] << "->";
        cur = shortestPath[cur];
    }
    cout << toMin;
    return 0;
}